#include <linux/memblock.h>
#include <linux/minmax.h>

/**
 * memblock_double_array - double the size of the memblock regions array
 * @type: memblock type of the regions array being doubled
 * @new_area_start: starting address of memory range to avoid overlap with
 * @new_area_size: size of memory range to avoid overlap with
 *
 * Double the size of the @type regions array. If memblock is being used to
 * allocate memory for a new reserved regions array and there is a previously
 * allocated memory range [@new_area_start, @new_area_start + @new_area_size]
 * waiting to be reserved, ensure the memory used by the new array does
 * not overlap.
 *
 * Return:
 * 0 on success, -1 on failure.
 */
static int __init_memblock memblock_double_array(struct memblock_type *type,
						phys_addr_t new_area_start,
						phys_addr_t new_area_size)
{
    return -1;//todo
}

/* adjust *@size so that (@base + *@size) doesn't overflow, return new size */
static inline phys_addr_t memblock_cap_size(phys_addr_t base, phys_addr_t *size)
{
    return *size = min(*size, PHYS_ADDR_MAX - base);
}

#define for_each_memblock_type(i, memblock_type, rgn) \
    for (i = 0, rgn = &memblock_type->regions[0];     \
         i < memblock_type->cnt;                      \
         i++, rgn = &memblock_type->regions[i])

/**
 * memblock_merge_regions - merge neighboring compatible regions
 * @type: memblock type to scan
 * @start_rgn: start scanning from (@start_rgn - 1)
 * @end_rgn: end scanning at (@end_rgn - 1)
 * Scan @type and merge neighboring compatible regions in [@start_rgn - 1, @end_rgn)
 */
static void __init_memblock memblock_merge_regions(struct memblock_type *type,
                                                   unsigned long start_rgn,
                                                   unsigned long end_rgn)
{
    int i = 0;
    if (start_rgn)
        i = start_rgn - 1;
    end_rgn = min(end_rgn, type->cnt - 1);
    while (i < end_rgn)
    {
        struct memblock_region *this = &type->regions[i];
        struct memblock_region *next = &type->regions[i + 1];

        if (this->base + this->size != next->base ||
            memblock_get_region_node(this) !=
                memblock_get_region_node(next) ||
            this->flags != next->flags)
        {
            BUG_ON(this->base + this->size > next->base);
            i++;
            continue;
        }

        this->size += next->size;
        /* move forward from next + 1, index of which is i + 2 */
        memmove(next, next + 1, (type->cnt - (i + 2)) * sizeof(*next));
        type->cnt--;
        end_rgn--;
    }
}

/**
 * memblock_insert_region - insert new memblock region
 * @type:	memblock type to insert into
 * @idx:	index for the insertion point
 * @base:	base address of the new region
 * @size:	size of the new region
 * @nid:	node id of the new region
 * @flags:	flags of the new region
 *
 * Insert new memblock region [@base, @base + @size) into @type at @idx.
 * @type must already have extra room to accommodate the new region.
 */
static void __init_memblock memblock_insert_region(struct memblock_type *type,
                                                   int idx, phys_addr_t base,
                                                   phys_addr_t size,
                                                   int nid,
                                                   enum memblock_flags flags)
{
    struct memblock_region *rgn = &type->regions[idx];

    BUG_ON(type->cnt >= type->max);
    memmove(rgn + 1, rgn, (type->cnt - idx) * sizeof(*rgn));
    rgn->base = base;
    rgn->size = size;
    rgn->flags = flags;
    memblock_set_region_node(rgn, nid);
    type->cnt++;
    type->total_size += size;
}

static int memblock_add_range(struct memblock_type *type,
                              phys_addr_t base, phys_addr_t size,
                              int nid, enum memblock_flags flags)
{
    bool insert = false;
    phys_addr_t obase = base;
    phys_addr_t end = base + memblock_cap_size(base, &size);
    int idx, nr_new, start_rgn = -1, end_rgn;
    struct memblock_region *rgn;

    if (!size)
        return 0;

    /* special case for empty array */
    if (type->regions[0].size == 0)
    {
        type->regions[0].base = base;
        type->regions[0].size = size;
        type->regions[0].flags = flags;
        type->total_size = size;
        type->cnt = 1;

        return 0;
    }

    /*
     * The worst case is when new range overlaps all existing regions,
     * then we'll need type->cnt + 1 empty regions in @type. So if
     * type->cnt * 2 + 1 is less than or equal to type->max, we know
     * that there is enough empty regions in @type, and we can insert
     * regions directly.
     */
    if (type->cnt * 2 + 1 <= type->max)
        insert = true;

repeat:
    /*
     * The following is executed twice.  Once with %false @insert and
     * then with %true.  The first counts the number of regions needed
     * to accommodate the new area.  The second actually inserts them.
     */
    base = obase;
    nr_new = 0;

    for_each_memblock_type(idx, type, rgn)
    {
        phys_addr_t rbase = rgn->base;
        phys_addr_t rend = rbase + rgn->size;

        if (rbase >= end)
            break;
        if (rend <= base)
            continue;
        /*
         * @rgn overlaps.  If it separates the lower part of new
         * area, insert that portion.
         */
        if (rbase > base)
        {
#ifdef CONFIG_NUMA
            WARN_ON(nid != memblock_get_region_node(rgn));
#endif
            WARN_ON(flags != MEMBLOCK_NONE && flags != rgn->flags);
            nr_new++;
            if (insert)
            {
                if (start_rgn == -1)
                    start_rgn = idx;
                end_rgn = idx + 1;
                memblock_insert_region(type, idx++, base,
                                       rbase - base, nid,
                                       flags);
            }
        }
        /* area below @rend is dealt with, forget about it */
        base = min(rend, end);
    }

    /* insert the remaining portion */
    if (base < end)
    {
        nr_new++;
        if (insert)
        {
            if (start_rgn == -1)
                start_rgn = idx;
            end_rgn = idx + 1;
            memblock_insert_region(type, idx, base, end - base,
                                   nid, flags);
        }
    }

    if (!nr_new)
        return 0;

    /*
     * If this was the first round, resize array and repeat for actual
     * insertions; otherwise, merge and return.
     */
    if (!insert)
    {
        while (type->cnt + nr_new > type->max)
            if (memblock_double_array(type, obase, size) < 0)
                return -ENOMEM;
        insert = true;
        goto repeat;
    }
    else
    {
        memblock_merge_regions(type, start_rgn, end_rgn);
        return 0;
    }
}
